A Disruption Tolerant Network is a wireless multi-hop network including a plurality of communication nodes. The Disruption Tolerant Network can be regarded as a Delay Tolerant Network and as a Disconnect Tolerant Network. Disruption/Delay/Disconnect Tolerant Networks are herein referred to collectively as “DTN”. In a DTN, a number of communication nodes (hereinafter referred to as “DTN nodes”) autonomously relay a message (data bundle or data packet), thereby achieving the delivery of the message from a source node to a destination node. One or both of the source node and the destination node may belong to the DTN (i.e., DTN nodes) or belong to an external network (e.g., the Internet, a public cellular network, or a wireless Local Area Network (LAN)). If one or both of the source node and the destination node belong to an external network, any one of the DTN nodes serves as a router or a gateway that relays messages between the DTN and the external network.
The DTN is based on the premise that a temporary or intermittent communication disconnection could occur due to movement of DTN nodes, blocking of wireless signals caused by an obstacle, or the like. In other words, the DTN is based on the premise that at least at some point in time, there is no stable communication path between the source node and the destination node. To cope with the temporary or intermittent communication disconnection, each DTN node performs a store-and-forward operation. Accordingly, the DTN can also be regarded as a store-and-forward type wireless multi-hop network. Further, some or all of the plurality of DTN nodes constituting the DTN may be mobile terminals having mobility. In this regard, the DTN can also be regarded as a store-and-forward type wireless ad-hoc network. For example, it has been assumed that the DTN is used for emergency communications at the time of a disaster, and inter-vehicle communications and road-to-vehicle communications in Intelligent Transport Systems (ITS).
As described above, a DTN node performs a store-and-forward operation. That is, a DTN node temporarily stores messages, received from a certain DTN node and are destined for a destination node, in a memory (hereinafter called “message buffer”). Then, when communication with other DTN nodes becomes possible, the DTN node determines a forwarding destination and a message(s) to be forwarded thereto in accordance with a routing protocol and forwards the message(s) stored in the message buffer to the determined forwarding destination.
Various proposals for a routing protocol suitable for the DTN have been made. Epidemic routing, Spray and Wait, and PROPHET have been known as typical routing protocols for the DTN. The PROPHET is an abbreviation for “Probabilistic Routing Protocol using History of Encounters and Transitivity”. The Epidemic routing and the Spray and Wait do not use any information about a network state. In contrast to this, in the PROPHET, each DTN node stores a history of contacts in the past and uses this history to determine the forwarding destination of a message.
The Epidemic routing is an improved version of the primitive flooding mechanism. Specifically, each DTN node that supports the Epidemic routing manages information called a “summary vector”. The summary vector indicates identifiers of messages that have been stored in the message buffer of each DTN node. During a contact with an adjacent DTN node, each DTN node exchanges respective summary vectors with the adjacent DTN node, identifies a message(s) that is not possessed by that DTN node itself, and receives the identified message(s) from the adjacent DTN node.
The Spray and Wait is an improved version of the Epidemic routing. Similarly to the DTN node in the Epidemic routing, during contact with an adjacent DTN node, each DTN node exchanges respective summary vectors with the adjacent DTN node and receives a message(s) that is not possessed by that DTN node itself from the adjacent DTN node. In the Spray and Wait, when a message is generated in the source node, the maximum number of replications of that message allowed to the DTN is specified. In the Spray stage, the DTN node that possesses the message generates copies of the message until the number of replications reaches the specified maximum number, and gives copies of the message to other DTN nodes which the DTN node has encountered. When the number of replications reaches the specified maximum number (Wait stage), the DTN node holds the message without sending copies of that message to other DTN nodes, and only when the DTN node possessing the message has encountered the final destination node, the DTN node sends the message to the final destination node.
In the PROPHET, each DTN node exchanges metrics called “Delivery Predictability” in addition to the summary vectors with an adjacent DTN node. A Delivery Predictability P(A, B) indicates a probability that a DTN node A can deliver a message to a DTN node B. For example, in the case where a node A contacts with a node B, only when the node B has a Delivery Predictability for a destination node D higher than that of the node A (i.e., only when P(B, D) is higher than P(A, D)), the node A sends a message addressed to the destination node D to the node B.
Patent Literature 1 discloses an improvement in a message delivery between DTN nodes. Patent Literature 2 discloses an improvement in routing in a DTN.